home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Collection of Tools & Utilities
/
Collection of Tools and Utilities.iso
/
pascal
/
posbm.zip
/
POSBM.PAS
< prev
next >
Wrap
Pascal/Delphi Source File
|
1989-06-14
|
6KB
|
193 lines
{Benchmark program to demonstrate the speed difference
between the POS() in Turbo Pascal 4 or 5 brute-force
and the Boyer-Moore method function POSBM()
Program Author: Costas Menico (Dr. Dobbs, Jul 89
And a new function (posCh) added by Toad Hall
for when you just want to find a single char in a string.
Courtesy of David Kirschbaum, Toad Hall
(with a slight tweak to show the elapsed time
in a more understandable form)
}
PROGRAM Search;
uses Dos,Crt;
{Link in the POSBM Boyer-Moore function }
{$F+}
{$L POSBM}
FUNCTION posBM(Pat,S : STRING) : BYTE; EXTERNAL;
{and the posCh function}
{$L POSCH}
FUNCTION posCh(Ch : CHAR; S : STRING) : BYTE; EXTERNAL;
{$F-}
VAR
Pat,S : STRING;
Ch : CHAR;
i,j : INTEGER;
elapsed : WORD; {TH}
CONST
LONGLOOP = 2000;
STARTFLAG = TRUE;
FINISHFLAG = FALSE;
{Prints benchmark timing information }
PROCEDURE Tick;
{Wait until the DOS timer has just ticked a new second.
This kinda insures we don't get any "second" wraparound.
}
VAR
regs : registers;
thissec : BYTE;
BEGIN
regs.ah := $2C; {get current time}
MsDos(regs);
thissec := regs.dh; {remember this second}
REPEAT
regs.ah := $2C; {get current time}
MsDos(regs);
UNTIL regs.dh <> thissec; {until a new second}
END; {of Tick}
PROCEDURE ShowTime(Start : BOOLEAN);
{v1.1 Rewritten to
(1) Use Boolean parm to indicate whether Start or Finish time.
(2) Use local regs.
(3) Display elapsed time (in decisecs) if Finish.
(4) Insure we have a "fresh" second before starting.
}
VAR regs : registers;
BEGIN
IF Start THEN Tick; {wait for a new second}
regs.ah := $2C; {get start time}
MsDos(regs);
regs.ax := (regs.dh * 100) + regs.dl; {seconds*100 + deciseconds}
IF Start THEN BEGIN
Write ('Start ... ');
elapsed := regs.ax; {remember start}
END
ELSE BEGIN
elapsed := regs.ax - elapsed; {elapsed time}
WriteLn('Finished, decisecs: ', elapsed:6);
END;
END; {of ShowTime}
BEGIN {main}
ClrScr;
{Create a random string of length 255}
Randomize;
FOR i := 1 TO 255 DO
S[i] := CHR(Random(255)+1);
S[0] := CHR(255);
{Initialize a pattern string with the last five characters
in the random string as the pattern to search for.
}
Pat := Copy(S,251,5);
{First do a search with the regular POS function}
Writeln('String Search using Brute-Force Method');
ShowTime(STARTFLAG); {show Start time,
remember current decisecs}
FOR j := 1 TO LONGLOOP DO
i := POS(Pat,S); {do the search a few times Brute-force}
ShowTime(FINISHFLAG); {get finish time,
display elapsed decisecs}
Writeln('Pattern found at: ', i); {show string psn}
{Now do search with the POSBM() (Boyer-Moore) function}
Writeln('String Search using Boyer-Moore Method');
ShowTime(STARTFLAG); {show Start time,
remember current decisecs}
FOR j := 1 TO LONGLOOP DO
i := posBM(Pat,S); {do search a few times Boyer-Moore}
ShowTime(FINISHFLAG); {get finish time,
display elapsed decisecs}
Writeln('Pattern found at: ', i); {show string psn}
{Now to test our posCh function against both the normal
Pascal POS() and the posBM functions.
}
FillChar(S[1],255,'a');
Ch := 'z';
S[254] := Ch;
S[0] := CHR(255);
{First do a character search with the regular POS function}
Writeln('Character Search using Brute-Force Method');
ShowTime(STARTFLAG); {show Start time,
remember current decisecs}
FOR j := 1 TO LONGLOOP DO
i := POS(Ch,S); {do the search a few times Brute-force}
ShowTime(FINISHFLAG); {get finish time,
display elapsed decisecs}
Writeln('Character found at: ', i); {show string psn}
{Now do character search with the POSBM() (Boyer-Moore) function}
Writeln('Character Search using Boyer-Moore Method');
ShowTime(STARTFLAG); {show Start time,
remember current decisecs}
FOR j := 1 TO LONGLOOP DO
i := posBM(Ch,S); {do search a few times Boyer-Moore}
ShowTime(FINISHFLAG); {get finish time,
display elapsed decisecs}
Writeln('Character found at: ', i); {show string psn}
{Now do character search with the posCh() function}
Writeln('Character Search using Toad Hall posCh function');
ShowTime(STARTFLAG); {show Start time,
remember current decisecs}
FOR j := 1 TO LONGLOOP DO
i := posCh(Ch,S); {do search a few times}
ShowTime(FINISHFLAG); {get finish time,
display elapsed decisecs}
Writeln('Character found at: ', i); {show string psn}
Writeln;
Writeln('DONE .. PRESS ENTER');
ReadLn;
END.